16. 3Sum Closest(Medium)

题目描述

原题

Description:
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

原题翻译

描述：
给定一个由n个整数构成的数组nums和一个整数target，在nums中找到三个整数，使它们的总和最接近target。返回这三个整数的总和。您可以假设每个输入都只有一个答案。

例如:

给定数组 nums = [-1, 2, 1, -4], 和 target = 1.
最接近target的整数为2。(-1 + 2 + 1 = 2)

解法一

主要思想

这道题是第15题的加强版，解法与15题相似。

运行速度：超过了98.65%的解答。

内存使用：超过了100%的解答。

源码

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int cha = Integer.MAX_VALUE;
        int result = 0;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (result > 0 && nums[i] * 3 - target >= result) { 
                // 若result > 0，nums[i]与target的差大于result，后面的结果一定大于result。
                break;
            }
            if (i == 0 || nums[i] != nums[i - 1]) {
                int low = i + 1, high = nums.length - 1, sum = target - nums[i];
                while (low < high) {
                    if (nums[low] + nums[high] == sum) {
                        return target;
                    } else if (nums[low] + nums[high] < sum) {
                        if (sum - nums[low] - nums[high] < cha) {
                            cha = sum - nums[low] - nums[high];
                            result = target - cha;
                        }
                        low++;
                    } else {
                        if (nums[low] + nums[high] - sum < cha) {
                            cha = nums[low] + nums[high] - sum;
                            result = target + cha;
                        }
                        high--;
                    }
                }
            }
        }
        return result;
    }
}